//
//  main.cpp
//  DynamicScheme
//
//  Created by huge on 2021/8/4.
//  Copyright © 2021 huge. All rights reserved.
//

/**
 初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态
 
 
 (1)划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。
     (2)确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
 (3)确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
 
    (4)寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。
    一般，只要解决问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程（包括边界条件）。
 
 实际应用中可以按以下几个简化的步骤进行设计：
 （1）分析最优解的性质，并刻画其结构特征。
 （2）递归的定义最优解。
 （3）以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值
 （4）根据计算最优值时得到的信息，构造问题的最优解
 
 
 算法实现的说明
 
 动态规划的主要难点在于理论上的设计，也就是上面4个步骤的确定，一旦设计完成，实现部分就会非常简单。
 
 使用动态规划求解问题，最重要的就是确定动态规划三要素：
 
 （1）问题的阶段 （2）每个阶段的状态
 
 （3）从前一个阶段转化到后一个阶段之间的递推关系。
 
 递推关系必须是从次小的问题开始到较大的问题之间的转化，从这个角度来说，动态规划往往可以用递归程序来实现，不过因为递推可以充分利用前面保存的子问题的解来减少重复计算，所以对于大规模问题来说，有递归不可比拟的优势，这也是动态规划算法的核心之处。
 
 确定了动态规划的这三要素，整个求解过程就可以用一个最优决策表来描述，最优决策表是一个二维表，其中行表示决策的阶段，列表示问题状态，表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值（如最短路径，最长公共子序列，最大价值等），填表的过程就是根据递推关系，从1行1列开始，以行或者列优先的顺序，依次填写表格，最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。
 
 f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}
 
 算法实现的步骤
 
 1、创建一个一维数组或者二维数组，保存每一个子问题的结果，具体创建一维数组还是二维数组看题目而定，基本上如果题目中给出的是一个一维数组进行操作，就可以只创建一个一维数组，如果题目中给出了两个一维数组进行操作或者两种不同类型的变量值，比如背包问题中的不同物体的体积与总体积，找零钱问题中的不同面值零钱与总钱数，这样就需要创建一个二维数组。
 
 注：需要创建二维数组的解法，都可以创建一个一维数组运用滚动数组的方式来解决，即一位数组中的值不停的变化，后面会详细徐叙述
 
 2、设置数组边界值，一维数组就是设置第一个数字，二维数组就是设置第一行跟第一列的值，特别的滚动一维数组是要设置整个数组的值，然后根据后面不同的数据加进来变幻成不同的值。
 
 3、找出状态转换方程，也就是说找到每个状态跟他上一个状态的关系，根据状态转化方程写出代码。
 
 4、返回需要的值，一般是数组的最后一个或者二维数组的最右下角。
 ————————————————
 原文链接：https://blog.csdn.net/zw6161080123/article/details/80639932
**/
#include <iostream>

int getMaxValue(int arr[],int n){
    int max = arr[0];
    //从temp数组里取出最大的值
    for(int i=1;i<n;i++){
        
//        printf(":%d ",arr[i]);
        
        if(arr[i]>max){
            max = arr[i];
        }
    }
    return max;
}
int MaxChildArrayOrder(int a[]) {
    
    int arr[] = {3,1,4,1,5,9,2,6,5};
                 //0 1 2 3
    int n = 9;
    int temp[9] = {0};//temp[i]代表0...i上最长递增子序列
    for(int i=0;i<n;i++){
        temp[i] = 1;//初始值都为1
    }
    
    //状态改变：如上数组，数组下标为1的数字1小于下标为3的数字，所以tmp【1】备忘为1，而后面下标为2的数字有可能会加一，因为数字4大于1，所以当前temp【2】= temp【1】+1；下标为3的数字1和前面进行比较都不大于，所以状态不变；下标为4的数字5大于所有前面的数，所以temp肯定要加一，但是这个temp是数组中的最大值；

    for(int i=1;i<n;i++){

        for(int j=0;j<i;j++){
            printf("temp[j],(j,i),(%d,%d),%d,%d ",j,i,temp[j],temp[i]);

            if(arr[i]>arr[j]&&temp[j]+1>temp[i]){
                //如果有a[i]比它前面所有的数都大，则temp[i]为它前面的比它小的数的那一个temp+1取得的最大值
                temp[i] = temp[j]+1;
            }

        }
//        printf(";:%d ",temp[i]);

    }
    int max = temp[0];
    //从temp数组里取出最大的值
    for(int i=1;i<n;i++){
        
        printf(":%d ",temp[i]);

        if(temp[i]>max){
            max = temp[i];
        }
    }
    return max;
}


/**
 3、数组最大连续子序列和
 如arr[] = {6,-1,3,-4,-6,9,2,-2,5}的最大连续子序列和为14。即为：9,2,-2,5
 创建一个数组a，长度为原数组长度，不同位置数字a[i]代表0...i上最大连续子序列和，a[0]=arr[0]设置一个最大值max，
 初始值为数组中的第一个数字。当进来一个新的数字arr[i+1]时，判断到他前面数字子序列和sum[i]+arr[i+1]跟arr[i+1]哪个大，
 前者大就保留前者，后者大就说明前面连续数字加起来is a negative，可以all舍弃，从arr[i+1]开始，
 每次比较完都跟max比较一下，最后的max就是最大值。
 **/
template<class T>
int length(T& data)
{
    return sizeof(data)/sizeof(data[0]);
}

int MaxContinueArraySum(int a[]) {
    int n = 9;
    int len = sizeof(&a)/sizeof(a[0]);
    len = length(a);
    int max = a[0];
    int sum = a[0];
    int sumArray[9] = {0};
    for(int i=1;i<n;i++){
        
        // make sure the flow number is increase or decrease ,if positive ,sum = sum+a[i]
        // then change the max array at it's position.
        if (sum+a[i] > a[i])
            sum = sum+a[i];
        else
            sum = a[i];
        
        if(sum>=max){
            max = sum;
        }
        sumArray[i] = max;
        
    }
    for (int i = 0; i < n; ++i) {
        std::cout << sumArray[i] << "\t";
    }
    return max;
}

/**
 4、数字塔从上到下所有路径中和最大的路径
 
 数字塔是第i行有i个数字组成，从上往下每个数字只能走到他正下方数字或者正右方数字，求数字塔从上到下所有路径中和最大的路径，如有下数字塔
 
 3
 
 1    5
 
 8    4    3
 
 2    6    7    9
 
 6    2    3    5    1
 
 最大路径是3-5-3-9-5，和为25。我们可以分别从从上往下看跟从下往上看两种动态规划的方式去解这个题
 
 从上往下看：当从上往下看时，每进来新的一行，新的一行每个元素只能选择他正上方或者左左方的元素，也就是说，第一个元素只能连他上方的元素，最后一个元素只能连他左上方的元素，其他元素可以有两种选择，所以需要选择加起来更大的那一个数字，并把这个位置上的数字改成相应的路径值，具体过程如下图所示
 
 3                            3                            3                            3
 00
 1    5                      4    8                      4    8                      4    8
 10   11
 8    4    3                8    4    3                12   12  11             12   12   11
 20   21   22
 2    6    7    9          2    6    7    9           2    6    7    9         14   18   19   20
 
 6    2    3    5    1    6    2    3    5    1     6    2    3    5    1    20   20   22   25   21
 
 所以最大值就是最底层的最大值也就是25。

 原文链接：https://blog.csdn.net/zw6161080123/article/details/80639932

 **/

int getMaxSumFromNumberTower(int a[],int n)
{


    int sum = 0;
    int twoDArray[5][5] = {{3},{1,5},{8,4,3},{2,6,7,9},{6,2,3,5,1}};
    int statuArray[5] = {0};
    
    for (int i = 0; i<5; i++) {
        
        std::cout  << "\n";

        for (int j=0; j<i; j++) {
//            std::cout  << twoDArray[i][j] << "\t";
            statuArray[j] = twoDArray[i][j]+twoDArray[i-1][j];
            std::cout << "("<< i << "," << j << ")" << "\t" << twoDArray[i][j] << "\t" << twoDArray[i-1][j] << "\t" << statuArray[j];
        }
        
    }
    for (int i = 0; i<5;i++) {
         std::cout << statuArray[i] << "\n";
    }
    
//    int* array = a;
//    for (int i=0; i<n; i++) {
//        std::cout << array[i] << "\n";
//    }

    return sum;
}

int main() {
    std::cout << "Hello, World!" << std::endl;
//    int max = MaxChildArrayOrder(nullptr);
//    printf("max: %d\n",max);
    
    int temp[] = {6,-1,3,-4,-6,9,2,-2,5};
//    int max = MaxContinueArraySum(temp);
//    printf("MaxContinueArraySum:%d",max);

    int max = getMaxSumFromNumberTower(temp, sizeof(temp)/sizeof(int));
    
    return 0;
}
